package personal.leil.learning.binary;

/**
 * 局部最小值问题
 * <p>
 * 题目描述：
 * 在数组中，任意相邻的两个数都不相等，找到其中一个局部最小的数
 * 局部最小：左右两侧相邻的数都比其小
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-2
 */
public class LocalMinimum {

    public static int findLocalMinimum(int[] arr) {
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        return process(arr, 0, arr.length - 1);
    }


    /**
     * 找到局部最小的index
     *
     * @param arr source arr
     * @param L   left bound index
     * @param R   right bound index
     * @return result index
     */
    public static int process(int[] arr, int L, int R) {
        int M = L + ((R - L) >> 1);
        if (arr[M] > arr[M + 1]) {
            return process(arr, M, R);
        }
        if (arr[M] > arr[M - 1]) {
            return process(arr, L, M);
        }
        return M;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = {34, 23, 43, 54, 234, 54, 2, 4, 564, 54, 6, 2, 342, 43, 4, 243, 43, 45, 333333, 42, 64};
        int index = findLocalMinimum(arr);
        System.out.println("target num index for ②: " + index);
    }

}
